/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-03-28
 * Time: 22:32
 */
public class test_1 {
    /*给你⼀个整数数组 nums ，你可以对它进⾏⼀些操作。
每次操作中，选择任意⼀个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等
于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最⼤点数。*/
    public static int deleteAndEarn(int[] nums) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回
        int n = 10001;
        // 1. 预处理
        int[] arr = new int[n];
        for (int x : nums) arr[x] += x;

        // 2. dp
        // 创建 dp 表
        int[] f = new int[n];
        int[] g = new int[n];
        // 初始化
        f[0] = arr[0];
        // 填表
        for (int i = 1; i < n; i++) {
            f[i] = g[i - 1] + arr[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        // 返回值
        return Math.max(f[n - 1], g[n - 1]);
    }

    public static void main(String[] args) {

    }
}
